package algorithms;

import java.util.Arrays;
import java.util.List;
import java.util.Set;

import datastructures.HashTreeNode;
import datastructures.ItemSet;

/**
 * @author Yuval Kesten <blockquote> Apriori Algorithm implemetation. Based upon
 *         the paper by <b>Rakesh Agrawal,Ramakrishnan Srikant</b> -
 *         <strong>Fast Algorithms for Mining Association Rules (1994)</strong>
 *         </blockquote>
 */
public class Apriori extends Algo {

	HashTreeNode hashTreeRoot;

	public Apriori(String pathFormat, int startIndex, int endIndex, Set<String> alphabetSet) throws Exception {
		super(pathFormat, startIndex, endIndex, alphabetSet);
		hashTreeRoot = new HashTreeNode(0);
		root = hashTreeRoot;
	}

	protected void newBasket(String[] tmpBasket, HashTreeNode root) {
		Arrays.sort(tmpBasket);
		List<List<String>> subsets = Common.getSubsetsOfSize(tmpBasket, k, getAlphabet());
		boolean found = true;
		if (subsets == null)
			return;
		HashTreeNode traverser;
		HashTreeNode singletone;
		for (List<String> list : subsets) {
			traverser = root;
			if (traverser.childrens == null)
				continue;
			for (int i = 0; i < k; i++) {
				String word = list.get(i);
				if (traverser.childrens.containsKey(word)) {
					traverser = traverser.childrens.get(word);
					found = true;
				} else if (k == 1) {
					Algo.incStats(k);
					singletone = new HashTreeNode(1);
					singletone.set = new ItemSet();
					singletone.set.addItem(word);
					traverser.put(word, singletone);
					traverser = traverser.childrens.get(word);
					found = true;
				} else {
					found = false;
					break;
				}
			}
			if (found) {
				traverser.set.counter++;
			}
		}
	}

	@Override
	protected boolean endOfSingleIteration(double support, long basketIndex, boolean foundSomething) {
		if (!hashTreeRoot.pruneAtDepth(support, numOfBaskets, k))
			return false;// There are no more live itemsets of size K

		if (k == maxK)
			return false;
		if (!hashTreeRoot.discoverAtDepth(support, numOfBaskets, k))
			return false;// Didn't found new itemset, we can break

		k++;

		return true;
	}

	@Override
	protected void init() {
		hashTreeRoot.depth = 0;
		hashTreeRoot.set = null;
	}

	@Override
	protected boolean processSingleLine(String line, double support) {
		String[] tmpBasket = Common.parseLineToBasket(line);
		numOfItems += tmpBasket.length;
		numOfBaskets++;
		newBasket(tmpBasket, hashTreeRoot);
		return true;// We never stop at end of single line
	}

	@Override
	protected void startOfSingleIteration() {
		iterNum++;
		numOfItems = 0;
		numOfBaskets = 0;
	}
}
